package leetcode.code1011;

import leetcode.helper.H;

public class Solution {
	public int shipWithinDays(int[] weights, int days) {
		int max = Integer.MIN_VALUE;
		int sum = 0;
		for (int w : weights) {
			max = Math.max(w, max);
			sum += w;
		}
		int l = max, r = sum;//
		int ans = 0;
		while (l <= r) {
			int mid = l + ((r - l) >> 1);
			int cur = mid, cnt = 1;
			for (int i = 0; i < weights.length; i++) {
				int num = weights[i];
				if (cur >= num) {
					cur -= num;
				} else {
					cur = mid - num;
					cnt++;
				}
			}
			if (cnt <= days) {
				ans = mid;
				r = mid - 1;
			} else {
				l = mid + 1;
			}
		}
		return ans;
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.shipWithinDays(H.str2array3("[1,2,3,1,1]"), 4);
	}
}
